<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>无标题文档</title>
<script>
/******************************************
**	二叉树中，
**	位于树顶部的节点叫做根节点
**	根节点没有父节点
**	树中的每个元素都叫做节点
**	节点分为内部节点和外部节点
**	至少有一个子节点的节点是内部节点
**	没有子元素的节点成为外部节点或叶节点
**
**	二叉搜索树(BST)是二叉树中的一种，
**	它只允许你在左侧节点存储（比父节点）小的值，
**	右侧节点存储（比父节点）大（或者等于）的值
*****************************************/

//	二叉搜索树
function BinarySearchTree(){
	var Node = function(key){
		this.key = key;
		this.left = null;
		this.right = null;
	}
	var root = null;
	
	//	插入一个节点
	this.insert = function(key){
		var node = new Node(key);
		if (root === null){
			root = node;
		}else{
			insertNode(root, node);
		}
	}
	
	//	中序遍历（以从小到大的顺序访问所有节点）
	this.inOrderTraverse = function(callback){
		inOrderTraverseNode(root,callback);
	}
	
	//	先序遍历
	this.preOrderTraverse = function(callback){
		preOrderTraverseNode(root,callback);
	}
	
	//	后序遍历
	this.postOrderTraverse = function(callback){
		postOrderTraverseNode(root,callback);
	}
	
	//	insert函数的辅助函数，找到新节点应该插入的正确位置
	var insertNode = function(node,newNode){
		if (node.key > newNode.key){
			if (node.left === null){
				node.left = newNode;
			}else {
				insertNode(node.left,newNode);
			}
		}else {
			if (node.right === null){
				node.right = newNode;
			}else {
				insertNode(node.right,newNode);
			}
		}
	}
	
	//	寻找最大值
	this.Min = function(){
		return minNode(root);
	}
	
	//	寻找最小值
	this.Max = function(){
		return maxNode(root);
	}
	
	//	查找一个特定值
	this.Search = function(key){
		return searchNode(root, key);
	}
	
	//	删除一个特定值
	this.Remove = function(key){
		root = removeNode(root, key);
		return root;
	}
	
	
	//	删除一个特定值Remove的辅助函数
	var removeNode = function (node, key){
		if (node === null){
			return null;
			
		//	如果要删除的值小于node的值
		}else if (node.key > key){
			node.left = removeNode(node.left, key);
			return node;
			
		//	如果要删除的值大于node的值
		}else if (node.key < key){
			node.right = removeNode(node.right, key);
			return node;
			
		//	如果要删除的值等于node的值
		}else if (node.key === key){
			//	如果该节点为叶节点
			if (node.left === null && node.right === null){
				node = null;
				return node;
			}
			
			//	如果该节点只有右子节点，没有左子节点
			if (node.left === null){
				node = node.right;
				return node;
				
			//	如果该节点只有左子节点，没有右子节点
			}else if (node.right === null){
				node = node.left;
				return node;
				
			//	该节点有两个子节点
			}else {
				var aux = findMinNode(node.right);
				node.key = aux.key;
				node.right = removeNode(node.right, aux.key);
				return node;
			}
		}
	}
	
	var findMinNode = function(node){
		if (node != null){
			while (node.left != null){
				return findMinNode(node.left);
			}
			return node;
		}else {
			return null;
		}
	}
	
	//	查找一个特定值Search的辅助函数
	var searchNode = function(node, key){
		if (node !== null){
			if (node.key > key){
				return searchNode(node.left, key);	
			}else if (node.key < key){
				return searchNode(node.right, key);
			}else {
				return true;
			}
		}else {
			return false;
		}
	}
		
	//	寻找最大值的辅助函数
	var minNode = function(node){
		if (node != null){
			while (node.left != null){
				return minNode(node.left);
			}
			return node.key;
		}else{
			return null;
		}
	}
	
	//	寻找最大值的辅助函数
	var maxNode = function(node){
		if (node != null){
			while (node.right != null){
				return maxNode(node.right);
			}
			return node.key;
		}else{
			return null;
		}
	}
	
	//	中序遍历的辅助函数（使用了递归，递归是堆栈）
	var inOrderTraverseNode = function(node, callback){
		/*****************************************
		**	当二叉树没有子节点时，输出左侧第一个叶结点
		**	输出之后程序会返回到堆栈的下一层
		**	也就是当前输出节点的根结点
		**	输出左侧叶结点的根节点后
		**	继续递归根节点的右子节点
		**	输出之后又回到堆栈的下一层
		**	以此类推，按从小到大的顺序输出所有的节点
		*****************************************/
		if (node != null){
			//	中序遍历是先左再根后右
			inOrderTraverseNode(node.left, callback);
			callback(node.key);
			inOrderTraverseNode(node.right, callback);
		}
	}
	
	//	先序遍历的辅助函数
	var preOrderTraverseNode = function(node, callback){
		if (node != null){
			callback(node.key);
			preOrderTraverseNode(node.left, callback);
			preOrderTraverseNode(node.right, callback);
		}
	}
	
	//	后序遍历的辅助函数
	var postOrderTraverseNode = function(node, callback){
		if (node != null){
			postOrderTraverseNode(node.left, callback);
			postOrderTraverseNode(node.right, callback);
			callback(node.key);
		}
	}
}

var tree = new BinarySearchTree();
tree.insert(12);
tree.insert(8);
tree.insert(6);
tree.insert(16);
tree.insert(18);
tree.insert(2);
tree.insert(23);
tree.insert(9);
tree.insert(13);
function printNode(value){
	console.log(value);
}
console.log(tree.Remove(12));
tree.inOrderTraverse(printNode);

</script>
</head>
</html>
